import java.util.LinkedList;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/5 10:06
 * @description:
 */
public class Solution79 {
    // 四个方向：右、左、下、上
    int[][] direction = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    boolean[][] visited; // 访问标记数组（类内复用，避免重复创建）

    public boolean exist(char[][] board, String word) {
        if (board == null || board.length == 0 || board[0].length == 0 || word.isEmpty()) {
            return false;
        }

        int rows = board.length;
        int cols = board[0].length;
        visited = new boolean[rows][cols];

        // 遍历所有可能的起点
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 只有起点字符匹配时才开始搜索
                if (board[i][j] == word.charAt(0)) {
                    // 标记起点为已访问
                    visited[i][j] = true;
                    // 递归搜索（当前索引为0，因为已经匹配了第0个字符）
                    if (backtrack(board, word, i, j, 0)) {
                        return true;
                    }
                    // 回溯：撤销起点的访问标记
                    visited[i][j] = false;
                }
            }
        }
        return false;
    }

    // 回溯函数：返回是否能从(x,y)开始匹配到word的index及以后字符
    private boolean backtrack(char[][] board, String word, int x, int y, int index) {
        // 终止条件：当前索引等于单词长度-1（所有字符都匹配成功）
        if (index == word.length() - 1) {
            return true; // 已经匹配完所有字符
        }

        // 探索四个方向
        for (int[] dir : direction) {
            int newX = x + dir[0];
            int newY = y + dir[1];

            // 检查新坐标是否合法（在矩阵内且未被访问）
            if (newX >= 0 && newX < board.length && newY >= 0 && newY < board[0].length
                    && !visited[newX][newY]) {

                // 检查下一个字符是否匹配
                if (board[newX][newY] == word.charAt(index + 1)) {
                    visited[newX][newY] = true; // 标记为已访问
                    // 递归搜索下一个字符，如果找到路径则返回true
                    if (backtrack(board, word, newX, newY, index + 1)) {
                        return true;
                    }
                    visited[newX][newY] = false; // 回溯：撤销访问标记
                }
            }
        }
        // 四个方向都无法匹配，返回false
        return false;
    }
    public static void main(String[] args) {
        Solution79 solution = new Solution79();
        System.out.println(solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED"));
        System.out.println(solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "SEE"));
        System.out.println(solution.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCB"));
    }

}
